package leetcode;

import java.util.Arrays;
import java.util.Stack;

public class LeetCodeMain96 {
    public int maximalSquare(char[][] matrix) {
        int x=matrix.length;
        int y=matrix[0].length;
        int max=0;
        int[][] dp=new int[x+1][y+1];
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                if (matrix[i-1][j-1]=='1'){
                    dp[i][j]=1+Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]));
                    max=Math.max(max,dp[i][j]);
                }
            }
        }
        return max*max;
    }
    public boolean isPalindrome(int x) {
        if (x<0){
            return false;
        }
        int sum=0;
        int x1=x;
        while (x1!=0){
            sum=sum*10+x1%10;
            x1/=10;
        }
        return sum==x;
    }
    public int threeSumClosest(int[] nums, int target) {
        int length=nums.length;
        int closeTarget=10000000;
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int pB=i+1;
            int pC=length-1;
            while (pB<pC){
                int sum=nums[i]+nums[pB]+nums[pC];
                if (sum==target){
                    return target;
                }
                if (Math.abs(sum - target) < Math.abs(closeTarget - target)) {
                    closeTarget = sum;
                }
                if (sum>target){
                    int p=pC-1;
                    while (pB<p&&nums[p]==nums[pC]){
                        p--;
                    }
                    pC=p;
                }else if (sum<target){
                    int p=pB+1;
                    while (p<pC&&nums[p]==nums[pB]){
                        p++;
                    }
                    pB=p;
                }
            }
        }
        return closeTarget;
    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int sum=m+n-1;
        int right1=m-1;
        int right2=n-1;
        while (right1>=0&&right2>=0){
            if (nums1[right1]>nums2[right2]){
                nums1[sum--]=nums1[right1--];
            }else {
                nums1[sum--]=nums2[right2--];
            }
        }
        if (right1>=0){
            while (right1>=0){
                nums1[sum--]=nums1[right1--];
            }
        }
        if (right2>=0){
            while (right2>=0){
                nums1[sum--]=nums2[right2--];
            }
        }
    }
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs);
        StringBuffer buffer=new StringBuffer();
        for (int i = 0; i < strs[0].length(); i++) {
            int count=1;
            char ch1=strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                char ch2=strs[j].charAt(i);
                if (ch1!=ch2){
                    break;
                }
                count++;
            }
            if (count!=strs.length){
                break;
            }
            buffer.append(ch1);
        }
        return buffer==null?"":buffer.toString();
    }
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
    }
    public String reverseWords(String s) {
        String[] arr=s.split(" ");
        String string="";
        for (int i = 0; i < arr.length-2; i++) {
            StringBuffer buffer =new StringBuffer(arr[i]);
            buffer.reverse();
            string+=buffer.toString()+" ";
        }
        StringBuffer buffer =new StringBuffer(arr[arr.length-1]);
        buffer.reverse();
        string+=buffer.toString();
        return string;
    }
    public void reverseString(char[] s) {
        int left=0;
        int right=s.length-1;
        while (left<right){
            char ch=s[left];
            s[left]=s[right];
            s[right]=ch;
            left++;
            right--;
        }
    }
    public int removeDuplicates(int[] nums) {
        if (nums.length==0||nums==null){
            return 0;
        }
        int count=1;
        int sum=Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]!=nums[i-1]&&sum!=nums[i]){
                count++;
            }else {
                sum=nums[i];
                nums[i]=Integer.MAX_VALUE;
            }
        }
        Arrays.sort(nums);
        return count;
    }
    public String multiply(String num1, String num2) {
        for (int i = num2.length()-1; i >=0 ; i--) {
            char ch1=num2.charAt(i);
            StringBuffer buffer=new StringBuffer();
            int sum=0;
            int num=ch1-'0';
            if (num==0&&i!=0){
                num1+="0";
                continue;
            }
            if (num==0&&i==0){
                return "0";
            }
            for (int j = num1.length()-1; j >= 0; j--) {
                char ch2=num1.charAt(j);
                int num3=ch2-'0';
                sum+=num3*num;
                buffer.append(sum%10);
                sum=sum/10;
                if (num3==0&&j==0){
                    return "0";
                }
            }
            if (sum!=0){
                buffer.append(sum);
            }
            buffer.reverse();
            num1=buffer.toString();
        }
        return num1;
    }
}
